Scroll Progress Bar

Quick sort

Quick sort is a highly efficient and widely used sorting algorithm that uses a divide-and-conquer approach to sort an array. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. Here's a C++ implementation of quick sort with comments and Sample Output.

Program:

    #include <iostream>
    #include <vector>
    
    // Function to partition the array into two sub-arrays, elements <= pivot and elements > pivot
    int partition(std::vector& arr, int low, int high) {
        int pivot = arr[high]; // Choose the last element as the pivot
        int i = low - 1; // Index of the smaller element
    
        for (int j = low; j < high; j++) {
            // If the current element is less than or equal to the pivot
            if (arr[j] <= pivot) {
                i++; // Increment index of smaller element
                std::swap(arr[i], arr[j]); // Swap arr[i] and arr[j]
            }
        }
    
        // Swap arr[i+1] and arr[high] (pivot)
        std::swap(arr[i + 1], arr[high]);
    
        return i + 1;
    }
    
    // Quick sort function
    void quickSort(std::vector& arr, int low, int high) {
        if (low < high) {
            // Partition the array into two sub-arrays
            int pivotIndex = partition(arr, low, high);
    
            // Recursively sort the sub-arrays
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    int main() {
        std::vector arr = {64, 34, 25, 12, 22, 11, 90};
    
        std::cout << "Original array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        // Perform quick sort
        quickSort(arr, 0, arr.size() - 1);
    
        std::cout << "\nSorted array: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
    
        return 0;
    }
In this code:
  • partition is a function that takes the input array arr, the lower index low, and the higher index high as parameters. It selects the pivot element, partitions the array into two sub-arrays, and returns the index of the pivot element after partitioning.
  • quickSort is the main sorting function that recursively divides the input array into sub-arrays, partitions them, and sorts them.
  • In the main function, an input array is provided, and both the original and sorted arrays are printed.
Sample Output:

    Original array: 64 34 25 12 22 11 90 
    Sorted array: 11 12 22 25 34 64 90

As shown in the sample output, the input array is successfully sorted in ascending order using the quick sort algorithm.


question

answer

question2

answer2